HW#4 --- last modified January 28 2019 19:27:07..

Solution set.

Due date: Apr 23

Files to be submitted:
  Hw4.zip

Purpose:

Related Course Outcomes: To experiment with some fo the number theoretic algorithms we have discussed.

The main course outcomes covered by this assignment are:

CLO6 -- Analyze or code a number theoretic algorithm

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw4.zip file. The written part should be in a file Hw4.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Consider the variant of the paging problem where requests come in as before, but now a request can either be for a single page or two contiguous pages. How does this affect the number of cache misses MIN makes in the worst case? How does it affect our lower bound `C_R^(obl) ge H_k`? (State any assumptions you make). How competitive is the Marker algorithm in this case? (Give a reasonable upper bound).
2. Use the extended Euclidean algorithm to find the multiplicative inverse of `7 mod 165`. Solve `8x = 6 mod 10` for all solutions.
3. Using the Chinese Remainder theorem determine a number x mod 165 that satisfies `x mod 3 = 2`, `x = 3 mod 5`, and `x = 8 mod 11`.
4. Suppose `p =11`, `q = 13`. If we choose `e = 7`, what would be a the RSA public and private keys? Show the result of encrypting with the private key, the message 97. Show the steps in decrypting it, to get the original number back.

For the coding part of the homework, I want you to code either a Java or python implementation of the Miller Rabin algorithm. I will run your program from the command line using the format:

java MillerRabin some_long_binary_string num_trials

or

python MillerRabin.py some_long_binary_string num_trials

For example,

java MillerRabin 11101110100101 10

On which input, your program should either output "Probably Prime" if it passes all the trials, or "Composite" if it does not. In this particular, case the number is prime, so it should output "Probably Prime".

Point Breakdown